#ifndef _LIBMUNIX_HASHTABLE_H_
#define _LIBMUNIX_HASHTABLE_H_

/*
 * Some code (C) 2004 Sun Microsystems, Inc. All rights reserved.
 */

int (*HashFunction)(uint32_t, void *);
int (*HashCompare) (uint16_t, uint16_t);

template<class T>
class HashTable;

template<class T>
struct HashNode
{
	HashNode(const T & t) : item(t), next(0) { }
	~HashNode() { if (next) delete next;}
	T			item;
	HashNode *	next;
};

template<class T>
class HashTable
{
public:
	HashTable(uint8_t n, HashFunction hf, HashCompare hc) {
		numBuckets = n;
		hashFunction = hf;
		hashCompare = hc;
		buckets = new HashNode[numBuckets];
		for (int i = 0; i < numBuckets; i++)
			buckets[i] = 0;
	}
	virtual ~HashTable() {
		// Buckets take care of deleting their next so this
		// kicks off a chain of deletes
		delete buckets[0];
		delete [] buckets;

//		for(int i = 0; i < numBuckets; i++)
//		{
//			if (buckets[i])
//				delete buckets[i];
//		}
//		delete [] buckets;
	}

	// TODO fix these dayum errors.
	uint32_t	Add(const T & t) {
		uint32_t bucket = hashFunction(numBuckets,t);
		if (buckets[bucket]) {	// one here, chain it
			while(buckets[bucket++]);

			buckets[bucket] = new HashNode(t);
//			buckets[bucket-1]->next = buckets[bucket];
		}
		return bucket;
	}

	void	Remove(const T & t) {
//		uint32_t key = hashFunction(numBuckets,t);
//		if (buckets[key]) {
//			if (buckets[key].item == t) {
//				if ((buckets[key])->next) {
//					HashNode * del = buckets[key];
//					buckets[key] = buckets[key]->next;
//					delete del;
//				}
//			} else if (buckets[key]->next) {
//
//			}
//		}
	}

//	void	Remove(uint32_t key) {
//		(buckets[key])->next = buckets[key];
//		delete buckets[key];
//	}

protected:
	uint32_t		numBuckets;
	HashNode **		buckets;
	HashFunction	hashFunction;
	HashCompare		hashCompare;
};



static inline uint32_t DefaultHash(uint32_t nbuckets, void * data)
{
	return (data % nbuckets);
}

static inline int DefaultCompare(uint32_t k1, uint32_t k2)
{
	return (k1 == k2);
}

static inline int HashString(uint32_t nbuckets, void * str)
{
	char * ptr = (char*)str;
	const char * c;
	ulong_t g;
	int h = 0;

	for (c = ptr; *c; c++)
	{
		h = (h << 4) + *c;
		if ((g = (h & 0xf0000000)) != 0) {
			h ^= (g >> 24);
			h ^= g;
		}
	}
	return (h % nbuckets);
}



#endif /* HASHTABLE_H_ */
